
/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode.cn/problems/merge-two-sorted-lists/
 */
public class mergeTwoLists {
    public static void main(String[] args) {
        mergeTwoLists mergeTwoLists = new mergeTwoLists();
        ListNode list1 = getListNode(421);
        ListNode list2 = getListNode(431);
        ListNode listNode = mergeTwoLists.mergeTwoLists_2(list1, list2);
        System.out.println(listNode);
        System.out.println(getNumByListNode(listNode));
    }

    /**
     * 自己的解决方案
     * <p>
     * 134和124本地输出正常，提交输出不正常（已解决，本地和网站入参不同（链表方向相反了））
     * <p>
     * 0 ms（100.00%）	40.8 MB（58.82%）
     *
     * @return
     */
    public ListNode mergeTwoLists_1(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) return null;
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        ListNode head = null, tail = null;
        while (list1 != null && list2 != null) {
            System.out.println(list1.val + ":" + list2.val);
            if (list1.val < list2.val) {
                if (head == null) {
                    head = tail = new ListNode(list1.val);
                } else {
                    tail.next = new ListNode(list1.val);
                    tail = tail.next;
                }
                list1 = list1.next;
            } else if (list1.val > list2.val) {
                if (head == null) {
                    head = tail = new ListNode(list2.val);
                } else {
                    tail.next = new ListNode(list2.val);
                    tail = tail.next;
                }
                list2 = list2.next;
            } else {
                if (head == null) {
                    head = tail = new ListNode(list1.val);
                } else {
                    tail.next = new ListNode(list1.val);
                    tail = tail.next;
                }
                tail.next = new ListNode(list2.val);
                tail = tail.next;
                list1 = list1.next;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }
        return head;
    }

    /**
     * 0 ms（100.00%）	40.6 MB（90.34%）
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists_2(ListNode list1, ListNode list2) {
        // 待输出链表的头部
        ListNode head = new ListNode();
        // 待输出链表的 last 结点
        ListNode last = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                last.next = list2;
                list2 = list2.next;
            } else {
                last.next = list1;
                list1 = list1.next;
            }
            last = last.next;
        }
        // list1 或 list2 可能还有剩余结点没有合并，
        if (list1 != null) last.next = list1;
        if (list2 != null) last.next = list2;
        return head.next;
    }

    /**
     * 根据数字获取ListNode
     *
     * @param val
     * @return 逆序链表
     */
    static ListNode getListNode(int val) {
        String[] split = String.valueOf(val).split("");
        ListNode obj = null;
        for (String s : split) {
            obj = new ListNode(Integer.parseInt(s), obj);
        }
        return obj;
    }

    /**
     * 根据listNode获取数字
     *
     * @param listNode
     * @return
     */
    static int getNumByListNode(ListNode listNode) {
        int num = listNode.val;
        int count = 1;
        while (listNode.next != null) {
            listNode = listNode.next;
            num = (int) (listNode.val * Math.pow(10, count) + num);
            count++;
        }
        return num;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
